网络数据中社区数选择方法综述

我们将从以下几个方面和大家分享网络数据中社区数选择方法综述：首先，我们简要说明研究问题的背景；然后，针对随机区块模型，我们介绍三种社区数选择方法类型：（1）基于贝叶斯信息准则（BIC）的模型选择方法；（2）基于网络交叉验证（NCV）的模型选择方法；（3）基于伪似然比（Pseudo likelihood ratio）统计量的模型选择方法。

1. 研究背景说明

网络社区发现是网络数据分析最热门的研究主题之一，目前已有许多关于网络社区检测的算法，包括，模块度最大化 (Newman, 2006; Good et al., 2010)，谱聚类 (Ng et al., 2002; Von Luxburg, 2007; Rohe et al., 2011)，伪似然方法 (Amini et al., 2013; Wang et al., 2021) 等。类似K均值聚类算法，这些社区检测算法通常需要提前给定社区数。并且给定的社区数直接决定算法的划分结果，如图1所示。然而，实际中的网络数据都是很难能看出或者简单确定有效的社区数，因此研究如何确定网络数据的社区数是非常重要的。

图1: 关于美国政治的书籍网络的划分。基于多种社区数推断的社区分配，其中相同颜色节点属于同一个簇 （Kawamoto，2017）。

随机区块模型是应用最广泛的随机图模型之一，最早由（Holland et al., 1983）提出在网络节点的连接概率中融入网络社区结构信息。对于一个具有个节点的无向网络，若可划分为个社区，那么随机区块模型可通过两个参数刻画，一个是网络节点标签向量，其中表示节点的社区属性；另一个是对称的区块概率矩阵B，其中表示(k, l)社区之间节点的连接概率。具体的，用对称的邻接矩阵A表示网络G的连接关系，其中对于任意的(i, j)，表示节点对之间具有连接，否则，并且约定对角线元素。  那么对于给定的标签向量以及区块概率矩阵B，随机区块模型假定网络节点(i, j)的连接，其中。不失一般性，我们用表示该随机图模型。注意到在随机区块模型中，节点对(i, j)之间的连接概率只取决于节点i, j的社区属性，如图2所示。为了说明的方便，在本文中，我们假设观测的网络的潜在真实模型为。接下来，在随机区块模型的框架下，我们将详细介绍针对社区数选择的三种方法类型。

图2: 具有三个社区的随机区块模型。

2. 基于贝叶斯信息准则的社区数选择方法

基于贝叶斯信息准则的社区选择方法是目前理论最完善的，具体的可参考Daudin et al. (2008); Saldana et al. (2017); Wang and Bickel (2017)以及 Hu et al. (2020)。这里我们将结合Hu et al. (2020)的文章进行介绍。基于贝叶斯理论，Hu，(2020) 提出的修正化贝叶斯信息准则是标签向量的最大后验似然函数。为了说明，在模型下, 用向量表示区块概率矩阵B的上三角元素。接着，我们通过以下三步介绍该准则的推导。

（1）给出在下，观测的邻接矩阵的对数似然函数为，，其中和分别表示社区(k, l)之间的观测连接数以及最大连接数；（2）给出潜变量的先验分布，记为。用表示网络节点的所有可能的划分，即，其中表示社区数为时对应的所有可能划分。对于任意的K，假设社区划分服从均匀分布，即。此外，为了避免过拟合，设定的先验概率与其规模成反比，即。这里意味着选择较小的社区数可能性大，而表示偏向选择较大的社区数。按照这种方式，的先验分布可表示为, ，对于，其中；（3）确定标签向量的后验分布。考虑到，

其中为社区划分的似然函数。因此，，其中为的均匀先验分布。考虑到为常数，因此根据贝叶斯理论，我们将选择使得后验似然最大化的社区划分，也就是

利用贝叶斯近似有，

因此，基于社区划分的最大后验似然的修正化贝叶斯准则（CBIC） 为，

 （2.1）

针对修正化贝叶斯准则有以下几点说明。 第一，该算法在实际使用时，可以利用社区检测算法 得到估计社区标签，然后用 plug-in 估计量得到区块连接概率估计，代入 (2.1) 式可获得近似的修正化贝叶斯准则。第二，该算法存在超参数需要选取，文章中提到超参数的推荐选择为。第三，这里介绍该修正化贝叶斯准则一方面是考虑到其具有完整的理论性质保障，另一方面是基于计算效率考虑，通过上面提到的近似方法，该算法对一般规模的网络数据是计算可行的。下面给大家介绍不带罚的模型选择方法。

3. 基于网络交叉验证的模型选择方法

交叉验证是非常受欢迎的模型选择方法，这里我们将结合Chen and Lei (2018) 以及 Li (2020)的研究工作介绍基于交叉验证的模型选择方法。交叉验证通过在训练数据估计模型，然后利用测试数据上评价估计模型性能以避免过拟合情况。与独立数据点不同，网络数据中节点之间通过连接相互关联，因此为了将交叉验证方法应用到网络数据，需要采用不同的数据分割方式。接下来，基于不同的分割方式，我们分别介绍这两种交叉验证方法。

Chen and Lei (2018)提出了区块分割方法，具体来说，首先将节点集随机划分为两组，。然后，对所有的，将观测的连接作为训练数据，表示为，其中表示中节点数量。此外，将连接 ，作为测试数据可表示为。文章考虑利用测试集的对数似然函数评价估计模型效果，即

   （3.1）

接着，我们通过三步介绍该模型选择算法：（1）对于任意的候选社区数K，在测试数据上利用谱聚类算法获得网络社区划分；（2）利用plug-in估计方法获得；（3）将估计参数以及似然函数 (3.1) 得到。最后选取作为估计社区数。

后来，Li (2020)提出了网络节点对抽样方法。其主要想法是为了最大可能保持节点之间的连接关系，通过对网络节点对以概率进行简单随机采样，获取训练数据，未被选中的节点对作为测试数据。为了说明，记选中的节点对集合为，选中的节点对及相应的观测集合用表示。并且记未选中的节点对为，未选中的节点对及相应的观测用表示。接下来我们通过以下步骤具体说明如何选择社区数：(1)对于任意候选社区数K，对训练数据集应用矩阵填充方法，获得邻接矩阵的低秩估计;（2）对进行谱聚类获取网络社区节点标签估计 ;（3）利用plug-in 估计方法计算；（4）将估计参数 以及似然函数 (3.1) 得到评估值。最后选取最大评价值对应的社区数。

关于网络交叉验证模型选择方法这里做几点说明。 第一，为了方便说明，上面只交代了一折交叉验证的算法流程，多折交叉验证只需要将网络数据根据需要进行分割，然后通过平均评估值去选取最佳的社区数。第二，基于网络交叉验证的模型选择方法对一般规模的网络数据也是计算可行的。第三，该方法虽然应用范围广泛，但是针对过拟合情况目前没有完备的理论保障。

4.基于伪似然比统计量的模型选择方法

在这节本文将结合最近Ma (2021)的研究工作介绍基于似然比的模型选择方法。为了选择最佳的社区数，该方法对任意的候选，利用伪似然比统计量比较基于社区数为和的估计模型的拟合优度。并且考虑到计算成本，该算法将谱聚类方法与二分法相结合以提高计算效率。接下来，我们将给出算法实现过程，然后给出该算法相关说明。

为了说明方便，这里引入一些相关定义。在的假设下，连接概率矩阵可表示为，其中表示节点对的连接概率，为社区属性矩阵若，否则。此外，令表示节点的度，并且用表示对角度矩阵。那么，图拉普拉斯矩阵可以给出为。不妨把的谱分解表示为, , 其中满足。

首先，我们介绍结合谱聚类与二分法的社区标签估计算法。具体的，

    （1）对于任意的候选，利用谱聚类方法将网络划分为个簇。

• （i）令表示节点的嵌入向量。
• （ii）利用均值方法将划分为个簇，用表示估计的社区属性矩阵，同时记对应的社区分配为  。

    （2）应用二分法获得。具体的，首先通过以下步骤找到具有最大组内距离

的簇，然后把该簇细分为两个子簇。也就是，选择，并把

作为个簇的划分。因此，可获得其对应的社区标签。

基于社区属性矩阵的估计算法，我们介绍如何通过伪似然比统计量选择社区数。具体的，对于任意的候选，可根据以及分别计算概率矩阵的估计，分别记, 。然后，计算伪似然比统计量：

该似然比衡量的是基于和的估计模型的拟合优度。直觉上，当时，该伪似然比统计量的值会偏大，而当时，该统计量的值会达到最小值。因此，我们要识别的是该伪似然比统计量变化的拐点，也就是达到最大值对应的最小社区数，表示为

具体寻找该拐点方法可参考Ma,2021的算法2.

这里我们给基于伪似然比统计量的社区数选择方法补充几点说明。第一，为了统一我们主要介绍了针对随机区块模型的社区数选择，关于修正随机区块的模型选择可以参考Ma, (2021) 的工作。第二，该算法应用谱聚类结合二分法估计社区标签提高计算效率，因此对一般规模的网络数据也是计算可行的。第三，基于修正随机区块模型框架，该算法建立了伪似然估计量的一致性。

5.网络数据中社区数选择方法总结

上面基于随机区块模型我们介绍了三类社区数选择方法，并且针对各类方法做了必要的说明。基于此，我们继续讨论未来可行的研究方向。首先，我们这里讨论的是最简单最经典的随机图模型，然而复杂的实际网络通常需要更灵活的随机图模型刻画，因此需要探索相应的模型选择方法。然后，注意到目前的模型选择方法是针对单模无向图，了解到实际网络存在双模以及多模情形并且多模之间的节点的社区属性具有相关关系，因此如何为这类网络数据选择社区数也是值得研究的课题。另外，随着科技的进步，可获得的数据量也呈爆炸性增长，因此针对大规模网络数据如何高效识别社区数也是有趣的研究问题。

6.参考文献

 [1] Amini, A. A., Chen, A., Bickel, P. J., & Levina, E. (2013). Pseudo-likelihood methods for community detection in large sparse networks. The Annals of Statistics, 41(4), 2097-2122.

[2] Chen, K., & Lei, J. (2018). Network cross-validation for determining the number of communities in network data. Journal of the American Statistical Association, 113(521), 241-251.

[3] Daudin, J. J., Picard, F., & Robin, S. (2008). A mixture model for random graphs. Statistics and computing, 18(2), 173-183.

[4] Good, B. H., De Montjoye, Y. A., & Clauset, A. (2010). Performance of modularity maximization in practical contexts. Physical Review E, 81(4), 046106.

[5] Holland, P. W., Laskey, K. B., & Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social networks, 5(2), 109-137.

[6] Hu, J., Qin, H., Yan, T., & Zhao, Y. (2020). Corrected Bayesian information criterion for stochastic block models. Journal of the American Statistical Association, 115(532), 1771-1783.

[7] Kawamoto, T., & Kabashima, Y. (2017). Cross-validation estimate of the number of clusters in a network. Scientific reports, 7(1), 1-17.

[8] Li, T., Levina, E., & Zhu, J. (2020). Network cross-validation by edge sampling. Biometrika, 107(2), 257-276.

[9] Ma, S., Su, L., & Zhang, Y. (2021). Determining the number of communities in degree-corrected stochastic block models. Journal of Machine Learning Research, 22(69), 1-63.

[10] Newman, M. E. (2006). Finding community structure in networks using the eigenvectors of matrices. Physical review E, 74(3), 036104.

[11] Ng, A., Jordan, M., & Weiss, Y. (2001). On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 14.

[12] Rohe, K., Chatterjee, S., & Yu, B. (2011). Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics, 39(4), 1878-1915.

[13] Saldana, D. F., Yu, Y., & Feng, Y. (2017). How many communities are there?. Journal of Computational and Graphical Statistics, 26(1), 171-181.

[14] Von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and computing, 17(4), 395-416.

[15] Wang, J., Zhang, J., Liu, B., Zhu, J., & Guo, J. (2021). Fast network community detection with profile-pseudo likelihood methods. Journal of the American Statistical Association, 1-14.

[16] Wang, Y. R., & Bickel, P. J. (2017). Likelihood-based model selection for stochastic block models. The Annals of Statistics, 45(2), 500-528.

- END -